1436. Destination City

1. Question

You are given the array paths, where paths[i] = [cityA_i, cityB_i] means there exists a direct path going from cityA_i to cityB_i. Return the destination city, that is, the city without any path outgoing to another city.

It is guaranteed that the graph of paths forms a line without any loop, therefore, there will be exactly one destination city.

2. Examples

Example 1:

Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output: "Sao Paulo" 
Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".

Example 2:

Input: paths = [["B","C"],["D","B"],["C","A"]]
Output: "A"
Explanation: All possible trips are: 
"D" -> "B" -> "C" -> "A". 
"B" -> "C" -> "A". 
"C" -> "A". 
"A". 
Clearly the destination city is "A".

Example 3:

Input: paths = [["A","Z"]]
Output: "Z"

3. Constraints

• 1 <= paths.length <= 100
• paths[i].length == 2
• 1 <= cityA_i.length, cityB_i.length <= 10
• cityA_i != cityB_i
• All strings consist of lowercase and uppercase English letters and the space character.

4. References

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/destination-city 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

5. Solutions

class Solution {
  public String destCity(List<List<String>> paths) {
    HashSet<String> set = new HashSet<>();

    for (List<String> lst : paths) {
      set.add(lst.get(0));
    }
    for (List<String> lst : paths) {
      if (!set.contains(lst.get(1))) {
        return lst.get(1);
      }
    }
    return null;
  }
}